# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

root=TreeNode(3)
root.left=TreeNode(9)
root.right=TreeNode(20)
root.right.left=TreeNode(15)
root.right.right=TreeNode(7)

def zigzagLevelOrder(root):
    #空树的情况
    if not root:
        return []
    path=[root]
    ans=[]
    flag=0
    while len(path)>0:
        pathLen=len(path)
        print(pathLen)
        ansProcess=[]
        while pathLen>0:
            if flag==0:
                first=path.pop(0)
                ansProcess.append(first.val)
                # ans.append(first.val)
                print(first.val)
                if first.left!=None:
                    path.append(first.left)
                    print("left:",first.left.val)
                if first.right!=None:
                    path.append(first.right)
                    print("right:",first.right.val)
            else:
                last=path.pop(0)
                ansProcess.insert(0,last.val)
                if last.left!=None:
                    path.append(last.left)
                if last.right!=None:
                    path.append(last.right)
            pathLen -= 1
        ans.append(ansProcess[:])
        if flag==0:
            flag=1
        else:
            flag=0
    print(ans)
zigzagLevelOrder(root)